//
//  94. 二叉树的中序遍历.swift
//  Top600
//
//  Created by rjb on 2021/8/10.
//

import Foundation
class Solution94_2 {
    
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        var stack: [TreeNode] = []
        var cur = root
        while cur != nil || !stack.isEmpty {
            if let tmpCur = cur {
                stack.append(tmpCur)
                cur = tmpCur.left
            } else {
                cur = stack.removeLast()
                result.append(cur!.val)
                // 出栈一个节点时，看其右子树是否有可处理的节点
                cur = cur?.right
            }
        }
        return result
    }
    
    static func test() {
        let solution = Solution94_2()
        let node1 = TreeNode(1)
        let node2 = TreeNode(2)
        let node3 = TreeNode(3)
        
        node1.right = node2
        node2.left = node3
        
        let result  = solution.inorderTraversal(node1)
        print(result)
    }
}
